/**
 * 给定二维数组，从左上走到右下，每一步只能向右或者向左。
 * 问有多少种方法满足最后路径上的异或和等于K。K是事先给定的固定值，且范围[0, 16)
 * 二维数组规模是300*300
 * 令 Dijk 是到i/j位置且异或和为k的方案总数，则
 * Dijk = D[i-1][j][k^Aij] + D[i][j-1][k^Aij]
 * 最后输出D[N][M][K]
 */
class Solution {
public:
    int countPathsWithXorValue(vector<vector<int>>& grid, int k) {
        int K = k;
        using llt = long long;
        using vi = vector<llt>;
        const llt MOD = 1E9 + 7;
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<vi>> D(n + 1, vector<vi>(m + 1, vi(16, 0)));
        D[1][1][grid[0][0]] = 1;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                if(1 == i and 1 == j) continue;
                for(int k=0;k<16;++k){
                    (D[i][j][k] += D[i - 1][j][k ^ grid[i - 1][j - 1]]) %= MOD;
                    (D[i][j][k] += D[i][j - 1][k ^ grid[i - 1][j - 1]]) %= MOD;
                }
            }
        }
        return D[n][m][K];
    }
};